package traverse

import "../binarytree"

// import "encoding/binary"

type TreeNode = binarytree.TreeNode

// 递归
func inOrder(root *TreeNode) (ans []int) {
	inOrderHelper(root, &ans)
	return
}
func inOrderHelper(root *TreeNode, res *[]int) {
	if root != nil {
		inOrderHelper(root.Left, res)
		*res = append(*res, root.Val)
		inOrderHelper(root.Right, res)
	}
}

// 迭代版本
func inOrderNon(root *TreeNode) []int {
	// 使用栈  中序顺序是左-中-右
	if root == nil {
		return nil
	}
	var res []int
	stack := []*TreeNode{root}
	var cur *TreeNode = root
	for cur != nil || len(stack) != 0 {
		if cur != nil {
			// 当前节点入栈
			stack = append(stack, cur)
			cur = cur.Left
		} else {
			//当前节点可以访问
			cur = stack[len(stack)-1]
			stack = stack[:len(stack)-1] //出栈
			res = append(res, cur.Val)
			// 右节点入栈
			// if cur.Right != nil {
			// stack = append(stack, cur.Right)
			cur = cur.Right
			// }
		}
	}
	return res
}
